package leetcode;

import kotlinetc.println
import kotlin.math.max

//https://leetcode.com/problems/score-of-parentheses/


/**
Given a balanced parentheses string S, compute the score of the string based on the following rule:

() has score 1
AB has score A + B, where A and B are balanced parentheses strings.
(A) has score 2 * A, where A is a balanced parentheses string.


Example 1:

Input: "()"
Output: 1
Example 2:

Input: "(())"
Output: 2
Example 3:

Input: "()()"
Output: 2
Example 4:

Input: "(()(()))"
Output: 6


Note:

S is a balanced parentheses string, containing only ( and ).
2 <= S.length <= 50
 */
fun main(args: Array<String>) {

    scoreOfParentheses1("((())())").println()
}

//Classic Stack 经典的栈问题
fun scoreOfParentheses(S: String): Int {

    val stack = arrayListOf<Int>()

    if (S.isEmpty()) return 0

    var res = 0

    var i = 0

    while (i < S.length) {

        val c = S[i]

        if (c == '(') {
            //保存之前的结果
            stack.push(res)

            res = 0

        } else {


            res = stack.pop() + max(1, res * 2)
        }
        i++
    }


    return res
}

/**
 * O(1)解法
 */
//https://leetcode.com/problems/score-of-parentheses/discuss/141777/C%2B%2BJavaPython-O(1)-Space
fun scoreOfParentheses1(S: String): Int {
    var dep = 0
    var prev = ' '
    var res = 0
    for (s in S) {
        if (s == '(') dep++ else dep--
        if (s == ')' && prev == '(') res += 1 shl dep
        prev = s
    }
    return res
}

fun <T> ArrayList<T>.pop() = this.removeAt(this.lastIndex)

fun <T> ArrayList<T>.push(c: T) = this.add(c)

